package leetcode.editor.cn;

//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
// 
//
// 示例 2： 
//
// 
//
// 
//输入： heights = [2,4]
//输出： 4 
//
// 
//
// 提示： 
//
// 
// 1 <= heights.length <=10⁵ 
// 0 <= heights[i] <= 10⁴ 
// 
// Related Topics 栈 数组 单调栈 👍 1902 👎 0

import java.util.Stack;

//Java：【84】 - 柱状图中最大的矩形
public class LargestRectangleInHistogram_84{
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram_84().new Solution();
                // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int largestRectangleArea(int[] heights) {
        int res =0;
        int[] tmp = new int[heights.length+2];
        //System.arraycopy(heights, 0, tmp, 1, heights.length); // 两边加0，处理溢出
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek()!=-1 && heights[i]<heights[stack.peek()]){ // 不断对i左边的高个求面积，直到更矮的
                int h = heights[stack.pop()]; // i是pop右边的矮子
                // 此时peek为h左边的矮子
                res = Math.max(res, h*(i-stack.peek()-1));
            }
            stack.push(i);
        }
        while (stack.peek()!=-1){ // 处理最后一个，相当于i=heights.length
            int h = heights[stack.pop()]; // i是pop右边的矮子
            // 此时peek为h左边的矮子
            res = Math.max(res, h*(heights.length-stack.peek()-1));
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
